/**
 * streamsummary_bucket.cpp
 * Implementation of Stream-Summary datastructure using doubly linked list of buckets.
 *
 * @author Andreas Bok Andersen
 *
 *
 * */
#ifndef ENTRY
#include "entry.h"
#endif

#include <math.h>
#include "bucket.h"
#include <boost/range/adaptor/map.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/foreach.hpp>
#include <boost/assign.hpp>

typedef unordered_map<int, Bucket*> ENTRY_BUCKET_REF_MAP;
typedef unordered_map<int, Bucket> INT_BUCKET_MAP;

class StreamSummary: public Summary::Summary {

private:
	INT_ENTRY_MAP entries;
	ENTRY_BUCKET_REF_MAP e_b_map;
	INT_BUCKET_MAP buckets;

	Bucket* min_bucket;
	void add_item(int i, int j, float w);
	void increase(int i, int j, float w);
	void replace_min(int i, int j, float w);

public:
	StreamSummary(int k) :
			Summary::Summary(k) {
		this->min_bucket = NULL;
	}

	void insert(int i, int j, float w) {
		printf("\nInserting: (%d,%d,%.4f)\n", i,j,w);
		if (this->entries.find(hash_value(i, j)) != entries.end()) {
			cerr << "INCREASE" << endl;
			this->increase(i, j, w);
		} else if (this->entries.size() < this->k) {
			cerr << "ADD" << endl;
			this->add_item(i, j, w);
		} else {
			cerr << "REPLACE" << endl;
			replace_min(i, j, w);
		}
		cerr << "SUMMARY: " << this->buckets_to_string() << endl;
		printf("#Entries %d\t#ebmap %d\n",entries.size(),e_b_map.size());
	}

	ENTRY_VEC get_summary() {
		ENTRY_VEC summary;
		boost::copy(this->entries | boost::adaptors::map_values,
				std::back_inserter(summary));
		return summary;
	}

	void get_summary(Entry entries[]);
	void get_summary(ENTRY_VEC *entries);

	string buckets_to_string() {
		stringstream ss;
		/*Bucket min = this->buckets.find((*min_bucket).key)->second;*/
		Bucket min = *min_bucket;
		ss << min.to_string() << " -> ";
		while (min.next) {
			/*min = this->buckets.find((*min.next).key)->second;*/
			min = *min.next;
			ss << min.to_string() << " -> ";
		}
		return ss.str();
	}

	string to_string() {
		stringstream ss;
		INT_ENTRY_MAP::iterator it = this->entries.begin();
		for (; it != this->entries.end(); it++) {
			ss << it->second.to_string();
		}
		return ss.str();
	}
	Entry get_min_el();

	Bucket get_min_bucket() {
		return *min_bucket;
	}

};

void StreamSummary::add_item(int i, int j, float w) {
	int b_key = (int) ceil(w);
	printf("new key: %d\n", b_key);
	Entry *e = new Entry(i, j, w, 0.0);
	this->entries.insert(make_pair<int, Entry>((*e).hash, *e));
	e = &this->entries.find((*e).hash)->second;

	Bucket * bucket;
	if (this->min_bucket == NULL) {
		printf("%s", "min_bucket == 0\n");
		//bucket = new Bucket(b_key, NULL, NULL);
		this->buckets.insert(
				make_pair<int, Bucket>(b_key, *new Bucket(b_key, NULL, NULL)));
		bucket = &this->buckets.find(b_key)->second;
		(*bucket).add(e);
		/*this->buckets.find(b_key)->second.add(e);*/
		/*this->e_b_map.insert(make_pair<int, Bucket*>((*e).hash,&this->buckets.find(b_key)->second));*/
		this->e_b_map.insert(make_pair<int, Bucket*>((*e).hash, bucket));
		/*this->min_bucket = &this->buckets.find(b_key)->second;*/
		this->min_bucket = bucket;

	} else if (this->buckets.find(b_key) == this->buckets.end()) {
		printf("%s\n", "! has new_key ");
		Bucket _bucket = *min_bucket;
		printf("minbucket..key: %d\n", _bucket.key);
		while (_bucket.next && (*_bucket.next).key < b_key) {
			_bucket = *_bucket.next;
		}
		printf("%s: %d\n", "insertion bucket found ", _bucket.key);

		this->buckets.insert(
				make_pair<int, Bucket>(b_key,
						*new Bucket(b_key,
								&this->buckets.find(_bucket.key)->second,
								NULL)));
		this->buckets.find(b_key)->second.add(e);
		printf("%s\n", "created new bucket");

		if (_bucket.next) {
			/*(*bucket).next = (this->buckets.find(_bucket.key)->second).next;
			 (*(*bucket).next).prev = bucket;*/
			this->buckets.find(b_key)->second.next = (this->buckets.find(
					_bucket.key)->second).next;
			(*this->buckets.find(_bucket.key)->second.next).prev =
					&this->buckets.find(b_key)->second;
		}

		(this->buckets.find(_bucket.key)->second).next = &this->buckets.find(
				b_key)->second;
		this->e_b_map.insert(
				make_pair<int, Bucket*>((*e).hash,
						&this->buckets.find(b_key)->second));

	} else {
		printf("%s\n", "has new_key ");
		bucket = &this->buckets.find(b_key)->second;
		printf("before add: %d\n ", (*bucket).elements.size());

		this->buckets.find(b_key)->second.add(e);
		e_b_map.insert(
				make_pair<int>((*e).hash, &this->buckets.find(b_key)->second));
	}
	printf("buckets size: %d\n", buckets.size());
	printf("e_b size: %d\n", e_b_map.size());
	printf("bucket : %d #el: %d\n", this->buckets.find(b_key)->second.key,
			this->buckets.find(b_key)->second.elements.size());
	printf("min_bucket after increase: %d #el: %d\n", (*min_bucket).key,
			(*min_bucket).elements.size());
}
;

void StreamSummary::increase(int i, int j, float w) {
	Entry * e = &this->entries.find(hash_value(i, j))->second;
	printf("(%d, %d, %.3f)\n", e->i, e->j, e->weight);


	Bucket * curr_bucket = this->e_b_map.find(e->hash)->second;
	cerr << "curr_bucket: " << curr_bucket->to_string() << endl;

	float _w = w + e->weight;
	int _key = (int) ceil(_w);
	printf("new weight:  %.4f, new key: %d\n", _w, _key);
	e->weight = _w;
	printf("entry after update : %.3f\n",
			this->entries.find(hash_value(i, j))->second.weight);
	Bucket * _bucket;

	if (this->buckets.find(_key) != this->buckets.end()) {
		printf("%s\n", "has new key");
		if (curr_bucket->key != _key) {
			printf("%s\n", "(*curr_bucket).key != _key");
			this->e_b_map.find(e->hash)->second =
					&this->buckets.find(_key)->second;
			this->buckets.find(_key)->second.add(e);
			curr_bucket->remove(e);
			//this->buckets.find((*curr_bucket).key)->second.remove(e);
		}

	} else {
		printf("%s\n", "!has new key");
		Bucket tmp_bucket = *curr_bucket;
		while (tmp_bucket.next && tmp_bucket.next->key < _key) {
			tmp_bucket = *tmp_bucket.next;
		}

		printf("found insertion point: %d\n", tmp_bucket.key);
		this->buckets.insert(
				make_pair(_key,
						*new Bucket(_key,
								&this->buckets.find(tmp_bucket.key)->second,
								NULL)));

		this->buckets.find(_key)->second.add(e);
		curr_bucket->remove(e);

		printf("next is null %d\n",
				(this->buckets.find(tmp_bucket.key)->second.next == NULL));
		if (tmp_bucket.next) {
			printf("%s\n", "tmp_bucket.next == NULL");
			(this->buckets.find((*tmp_bucket.next).key)->second).prev =
					&this->buckets.find(_key)->second;
			printf("%s\n", "updated next.prev");
			this->buckets.find(_key)->second.next = (this->buckets.find(
					tmp_bucket.key)->second).next;
			printf("%s\n", "updated newbucket.next");
		}
		printf("%s\n", "updated next");
		(this->buckets.find(tmp_bucket.key)->second).next = &this->buckets.find(
				_key)->second;

		this->e_b_map.find(e->hash)->second =
				&this->buckets.find(_key)->second;
		printf("%s\n", "updated next2");
	}

	if (!curr_bucket->has_elements()) {
		printf("%s\n", "curr_bucket empty");
		if (curr_bucket == this->min_bucket) {
			this->min_bucket = this->min_bucket->next;
			this->min_bucket->prev = NULL;
		} else {
			if (curr_bucket->next) {
				printf("%s\n", "curr.next");
				curr_bucket->next->prev = curr_bucket->prev;
				/*this->buckets.find((*(*curr_bucket).next).key)->second.prev =
						this->buckets.find((*curr_bucket).key)->second.prev;*/
			}
			curr_bucket->prev->next = curr_bucket->next;
			/*this->buckets.find((*(*curr_bucket).prev).key)->second.next =
					&this->buckets.find((*(*curr_bucket).next).key)->second;*/
		}

		this->buckets.erase(curr_bucket->key);
		delete curr_bucket;
	}
}

Entry StreamSummary::get_min_el() {
	cerr << "get min el" << endl;
	printf("min_bucket get_min_el : %d\n", (*min_bucket).key);
	/*Bucket b = this->buckets.find((*this->min_bucket).key)->second;*/
	Bucket b = *this->min_bucket;
	cerr << b.to_string() << endl;
	ENTRY_P_SET::iterator it = b.elements.begin();
	Entry min_el = *(*it);
	for (; it != b.elements.end(); it++) {
		if ((*(*it)).weight < min_el.weight) {
			min_el = *(*it);
		}
	}
	printf("found min el: (%d,%d,%.3f)\n", min_el.i, min_el.j, min_el.weight);
	return min_el;
}

void StreamSummary::replace_min(int i, int j, float w) {
	Entry min = get_min_el();
	Entry *e = new Entry(i, j, w + (min).weight, (min).weight);
	int key = (int) ceil(e->weight);
	cerr << "replace el: " << e->to_string() << " new key: " << key << endl ;
	Bucket *bucket;
	this->entries.insert(make_pair<int, Entry>((*e).hash, *e));
	e = &this->entries.find((*e).hash)->second; // Pointer to new element
	printf("%s\n", "inserted entry ");
	if (this->buckets.find(key) != this->buckets.end()) {
		bucket = &this->buckets.find(key)->second;
		e_b_map.find(e->hash)->second = bucket;
		/*e_b_map.insert(make_pair<int>((*e).hash, bucket));*/
		cerr << "new key exists" << endl;
	} else {
		cerr << " new key !=exists, find insertion point" << endl;
		Bucket _bucket = *this->e_b_map.find((min).hash)->second;
		while (_bucket.next && _bucket.next->key < key) {
			_bucket = *_bucket.next;
		}

		this->buckets.insert(make_pair<int, Bucket>(key,
				*new Bucket(key,&this->buckets.find(_bucket.key)->second,NULL)));
		bucket = &this->buckets.find(key)->second;
		if (this->buckets.find(_bucket.key)->second.next) {
			bucket->next = (this->buckets.find(_bucket.key)->second).next;
			bucket->next->prev = bucket;
		}
		(this->buckets.find(_bucket.key)->second).next = bucket;

	}
	bucket->add(e);
	cerr << "added new bucket" << endl;
	Bucket * curr_bucket = this->e_b_map.find(min.hash)->second;
	printf("%s\n", "Found curr_bucket");
	(*curr_bucket).remove(&this->entries.find(min.hash)->second);
	cerr << "removed entry in curr_bucket" << endl;
	if (!(*curr_bucket).has_elements()) {
		cerr << "!curr_bucket has elements" << endl;
		if (curr_bucket == min_bucket) {
			cerr << "curr_bucket == min_bucket" << endl;
			this->min_bucket = &this->buckets.find((*(*min_bucket).next).key)->second;
			this->min_bucket->prev = NULL;
		} else {
			if ((*curr_bucket).next) {
				this->buckets.find((*(*curr_bucket).next).key)->second.prev = this->buckets.find((*curr_bucket).key)->second.prev;
			}
			(*(*curr_bucket).prev).next = (*curr_bucket).next;
		}
		this->buckets.erase(curr_bucket->key);
	}
	this->entries.erase((min).hash);
	printf("replace entry has bucket: %d\n", bucket->elements.find(e) != bucket->elements.end());
}

void StreamSummary::get_summary(Entry summary[]) {
	INT_ENTRY_MAP::iterator it;
	int i = 0;
	for (it = this->entries.begin(); it != this->entries.end(); it++) {
		summary[i] = it->second;
		i++;
	}
}

void StreamSummary::get_summary(ENTRY_VEC *summary) {
	boost::copy(this->entries | boost::adaptors::map_values,
			std::back_inserter(*summary));
}
